package com.zhang.third.day01;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @title: 有向无环图
 * @author: zhang
 * @date: 2022/4/1 14:54
 * {
 *   "source":["flatMap[0]","flatMap[1]"],
 *   "flatMap[0]":["reduce[0]","reduce[1]"],
 *   "flatMap[1]":["reduce[0]","reduce[1]"],
 *   "reduce[0]":["print"],
 *   "reduce[1]":["print"]
 * }
 */
public class Example3 {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> dag = new HashMap<>();

        ArrayList<String> sourceNeighbors = new ArrayList<>();
        sourceNeighbors.add("flatMap[0]");
        sourceNeighbors.add("flatMap[1]");
        dag.put("source", sourceNeighbors);

        ArrayList<String> flatMap0Neighbors = new ArrayList<>();
        flatMap0Neighbors.add("reduce[0]");
        flatMap0Neighbors.add("reduce[1]");
        dag.put("flatMap[0]", flatMap0Neighbors);

        ArrayList<String> flatMap1Neighbors = new ArrayList<>();
        flatMap1Neighbors.add("reduce[0]");
        flatMap1Neighbors.add("reduce[1]");
        dag.put("flatMap[1]", flatMap1Neighbors);

        ArrayList<String> reduce0Neighbors = new ArrayList<>();
        reduce0Neighbors.add("print");
        dag.put("reduce[0]", reduce0Neighbors);

        ArrayList<String> reduce1Neighbors = new ArrayList<>();
        reduce1Neighbors.add("print");
        dag.put("reduce[1]", reduce1Neighbors);

        topologySort(dag,"source","source");
    }

    //拓扑排序
    public static void topologySort(HashMap<String, ArrayList<String>> dag, String vertex, String result) {
        if (vertex.equals("print")) {
            System.out.println(result);
        } else {
            for (String v : dag.get(vertex)) {
                topologySort(dag, v, result + "=>" + v);
            }
        }
    }
    //topologySort(dag,"source","source");
    //topologySort(dag, flatMap[0], source => flatMap[0]);
    //topologySort(dag, reduce[0], source => flatMap[0] => reduce[0] );
    //topologySort(dag, print, source => flatMap[0] => reduce[0] => print );

}
